解題程式碼

var exist = function (board, word) {
  const DFS = (i, j, wordIndex) => {
    if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] !== word[wordIndex]) return false;
    if (wordIndex === word.length - 1) return true;

    board[i][j] = '.';
    let res = DFS(i + 1, j, wordIndex + 1) || DFS(i - 1, j, wordIndex + 1) || DFS(i, j + 1, wordIndex + 1) || DFS(i, j - 1, wordIndex + 1);
    board[i][j] = word[wordIndex]; // 經過上面條件判斷後，可以直接 restore 沒問題，因為 word[wordIndex] === 未修改前的 board[rowPos][colPos]
    return res;
  };

  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[0].length; j++) {
      if (DFS(i, j, 0)) return true;
    }
  }

  return false;
};

解題思路、演算法

這題使用 DFS + 回溯法，在搜尋的過程中判斷當前元素 + 索引是否對應到 word 該索引的字元，如果不匹配就結束遞迴，嘗試其他路徑。

題解有用 board[rowPos][colPos] = '.' 改寫走過的路徑，是為了避免例如，board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]、word = ABA 的時候，在 B 時 DFS 又找到 A，然後就回傳 true 的這種 bug。

題目提到 Follow up 的部分，有想到兩種狀況，也就是 Pruning（剪枝） 進行加速，提早回傳結果:

1. 字串 word 長度大於 board 大小
2. board 上缺少了 word 中的某個字元

解法的時間、空間複雜度

時間複雜度: O(m * n * 3^l)，l 是 word 長度，3^l 代表 DFS 往三個方向查找
空間複雜度: O(min(l, m * n))

參考資料

[LeetCode]79. Word Search 中文